package com.cn.algorithm02.class06;

/***
 * @author: hels
 * @description: https://leetcode.cn/problems/count-of-range-sum/
 * 给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/count-of-range-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 **/
public class C01_CountOfRangeSum {
/*    [-2147483647,0,-2147483647,2147483647]
            -564
            3864*/
    public static void main(String[] args) {
        int[] arr = {-2147483647, 0, -2147483647, 2147483647};
        int lower = -564, upper = 3864;
        System.out.println(countRangeSum(arr, lower, upper));
        System.out.println(Integer.toBinaryString(-2147483647));
    }

    public static int countRangeSum(int[] arr, int lower, int upper) {
        if (arr == null || arr.length == 0) return 0;
        // 前缀和  // 此处新的数组要使用long类型，因为original dataArray 取值范围是证书范围，求和会越界
        long[] sum = new long[arr.length];
        sum[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            sum[i] = sum[i-1] + arr[i];
        }

        return process(sum, 0, sum.length-1, lower, upper);
    }

    private static int process(long[] sum, int L, int R, int lower, int upper) {
        // base case
        if (L == R) {
            return sum[L]>=lower && sum[L]<=upper ? 1 : 0;
        }

        // L < R
        // 分递归块
        int mid = L + ((R-L)>>1);
        int leftNum = process(sum, L, mid, lower, upper);
        int rightNum = process(sum, mid+1, R, lower, upper);

        // 核心逻辑
        int mergeNum = merge(sum, L, mid, R, lower, upper);
        return leftNum + rightNum + mergeNum;
    }

    private static int merge(long[] sum, int L, int mid, int R, int lower, int upper) {
        int wl = L, wr = L; // 窗口滑动左右下标，左闭右开
        int ans = 0;
        for (int i = mid + 1; i <= R; i++) {
            long min = sum[i] - upper;
            long max = sum[i] - lower;
            while (wr <= mid && sum[wr] <= max) {
                wr++;
            }
            while (wl <= mid && sum[wl] < min) {
                wl++;
            }
            ans += wr - wl;
        }

        // 归并排序
        long[] sortArr = new long[R-L+1];
        int index = 0;
        int p1= L, p2 = mid+1;
        while (p1 <= mid && p2 <= R) {
            sortArr[index++] = sum[p1] <= sum[p2] ? sum[p1++] : sum[p2++];
        }
        while (p1 <= mid) {
            sortArr[index++] = sum[p1++];
        }
        while (p2 <= R) {
            sortArr[index++] = sum[p2++];
        }
        for (int i = 0; i < sortArr.length; i++) {
            sum[L+i] = sortArr[i];
        }

        return ans;
    }
}
